/* 654. 最大二叉树 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
function TreeNode(val, left, right) {
	this.val = val === undefined ? 0 : val
	this.left = left === undefined ? null : left
	this.right = right === undefined ? null : right
}
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
/* 递归 */
var constructMaximumBinaryTree = function (nums) {
	const construct = (nums, left, right) => {
		if (left < right) return null
		let best = left
		for (let i = left + 1; i <= right; ++i) {
			if (nums[i] > nums[best]) {
				best = i
			}
		}
		const node = new TreeNode(nums[best])
		node.left = construct(nums, left, best - 1)
		node.right = construct(nums, best + 1, right)
		return node
	}
	return construct(nums, 0, nums.length - 1)
}
/*  单调栈 */
var constructMaximumBinaryTree = (nums) => {
	const stack = []
	nums.push(10001) //哨兵值
	for (let i = 0; i < nums.length; i++) {
		// 因为出栈的时候构造树，所以栈中的元素都是节点
		const curNode = new TreeNode(nums[i])
		while (stack.length && stack[stack.length - 1].val < curNode.val) {
			// 出栈作为子节点
			const childNode = stack.pop()
			// 栈中无其他元素 或者 栈顶值是大于当前值的 [3,2,1]
			if (!stack.length || stack[stack.length - 1].val > curNode.val) {
				curNode.left = childNode
			} else {
				stack[stack.length - 1].right = childNode
			}
		}
		// 因为要出栈的时候构造树
		stack.push(curNode)
	}
	return stack[0].left
}

const res = constructMaximumBinaryTree([3, 2, 1, 6, 0, 5])
console.log('constructMaximumBinaryTree :>>', res)
